package com.linyaonan.leetcode.medium._56;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 *
 * 给出一个区间的集合，请合并所有重叠的区间。
 *
 * 示例 1:
 *
 * 输入: [[1,3],[2,6],[8,10],[15,18]]
 * 输出: [[1,6],[8,10],[15,18]]
 * 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 * 示例 2:
 *
 * 输入: [[1,4],[4,5]]
 * 输出: [[1,5]]
 * 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
 *
 *
 * @author: Lin
 * @date: 2020/4/16
 */
public class Merge {

    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) {
            return intervals;
        }
        // 将起始坐标作为排序因子排序
        Arrays.sort(intervals, Comparator.comparingInt(i -> i[0]));
        ArrayList<int[]> save = new ArrayList<>();
        int[] comp = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            int[] thisC = intervals[i];
            // 后一个数组的起始值小于等前一个值的结尾，表示可以合起来
            if (thisC[0] <= comp[1]) {
                // 结尾修改
                comp[1] = Math.max(comp[1], thisC[1]);
            } else {
                save.add(comp);
                comp = thisC;
            }
        }
        save.add(comp);
        int[][] result = new int[save.size()][2];
        for (int i = 0; i < result.length; i++) {
            result[i] = save.get(i);
        }
        return result;
    }

    public int[][] merge2(int[][] intervals) {
        // 1. 异常边界
        if (intervals.length == 1) {
            return intervals;
        }
        // 2. 首先按照starti 进行排序
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
        // 3. 依次比较starti数值，如果starti数值位于前一个数组的endi范围内，则表示这两个数组重合，可以进行合并，否则前一个与当前的不能合并
        int[] startCom = intervals[0];
        List<int[]> save = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            // 用于比较
            int[] c = intervals[i];
            // 合并操作
            if (c[0] <= startCom[1]) {
                startCom[1] = Math.max(startCom[1], c[1]);
            } else {
                save.add(startCom);
                startCom = c;
            }
        }
        // 最后一个数组不要遗漏
        save.add(startCom);
        // 4. 循环完成后将list还原数组
        int[][] r = new int[save.size()][2];
        int i = 0;
        for (int[] ints : save) {
            r[i++] = ints;
        }
        return r;
    }

}
